/*
 *  Min Priority Queue implemetation with a binary heap
 */
package algs4.ds;

import java.util.Random;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MinPQ<E extends Comparable<E>> implements Iterable<E>, Cloneable
{
    /* Inner Class */
    private class HeapIterator implements Iterator<E>
    {
        MinPQ<E> cp;

        public HeapIterator() {
            try {
                cp = MinPQ.this.clone();
            } catch (CloneNotSupportedException e) {
                e.printStackTrace();
            }
        }

        public boolean hasNext() { return !cp.isEmpty(); }
        public E       next()    { return cp.delMin();   }
    }

    /* Fields */
    private E[] pq; // binary heap
    private int sz; // size of PQ

    /* Constructors */
    public MinPQ() { pq = (E[]) new Comparable[4 + 1]; sz = 0; }

    /* Instance Methods */
    public boolean     isEmpty()  { return sz == 0;            }
    public int         size()     { return sz;                 }
    public Iterator<E> iterator() { return new HeapIterator(); }

    public MinPQ<E> clone() throws CloneNotSupportedException
    {
        MinPQ<E> cloned = (MinPQ<E>) super.clone();

        cloned.pq = (E[]) new Comparable[pq.length];
        System.arraycopy(pq, 1, cloned.pq, 1, sz);

        return cloned;
    }

    public void insert(E e) {
        // check whether PQ is full
        if (sz == pq.length - 1) resize(2 * sz);

        // update
        pq[++sz] = e;
        swim(sz);
    }

    public E delMin() {
        // check whether PQ is empty
        if (isEmpty()) throw new NoSuchElementException("Priority Queue underflow");

        // retrieve element
        E e = pq[1];

        // update
        pq[1]    = pq[sz];
        pq[sz--] = null;    // avoid loitering
        sink(1);

        // check whether usage rate is less than one quarter
        if (sz > 1 && sz == (pq.length - 1) / 4) resize(2 * sz);

        return e;
    }

    public E min() {
        // check whether PQ is empty
        if (isEmpty()) throw new NoSuchElementException("Priority Queue underflow");

        return pq[1];
    }

    /* Private Instance Methods */
    private void resize(int c) {
        assert c >= sz;

        E[] dst = (E[]) new Comparable[c + 1];
        System.arraycopy(pq, 1, dst, 1, sz);
        pq = dst;
    }

    private void swim(int k) {
        E e = pq[k];

        // swim
        while (k > 1 && e.compareTo(pq[k / 2]) < 0) {
            pq[k]  = pq[k / 2];
            k     /= 2;
        }

        pq[k] = e;
    }

    private void sink(int k) {
        E e = pq[k];

        // sink
        int i;
        while ((i = 2 * k) <= sz) {
            if (i < sz && pq[i].compareTo(pq[i + 1]) > 0) i++;

            if (e.compareTo(pq[i]) > 0) {
                pq[k] = pq[i];
                k     = i;
            } else {
                break;
            }
        }

        pq[k] = e;
    }

    /* Main Test */
    public static void main(String[] args) {
        Integer[] a = new Integer[25];
        Random    r = new Random(System.currentTimeMillis());

        for (int i = 0; i < 25; i++) a[i] = r.nextInt(100);

        // show data
        System.out.print("BF: ");
        for (int i = 0; i < 25; i++) System.out.printf("%2d ", a[i]);
        System.out.println();

        MinPQ<Integer> pq = new MinPQ<>();

        for (int i = 0; i < 25; i++) pq.insert(a[i]);

        // show data
        System.out.print("AF: ");
        // while (!pq.isEmpty()) System.out.printf("%2d ", pq.delMin());
        for (Integer i : pq) System.out.printf("%2d ", i);
        System.out.println();
    }
}
